package com.example.demo.leetcode.classics150;

import com.example.demo.kafka.KafkaController;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _62K个一组翻转链表
 * @description
 * @date 2023/07/28 16:41
 * <p>
 * ******************************************************
 */
public class _62K个一组翻转链表 {

    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) return null;
        // 区间 [a, b) 包含 k 个待反转元素
        ListNode a, b;
        a = b = head;
        for (int i = 0; i < k; i++) {
            // 不足 k 个，不需要反转，base case
            if (b == null) return head;
            b = b.next;
        }
        // 反转前 k 个元素
        ListNode newHead = reverse(a, b);
        // 递归反转后续链表并连接起来
        a.next = reverseKGroup(b, k);



        return newHead;
    }


    /* 反转区间 [a, b) 的元素，注意是左闭右开 */
    public ListNode reverse(ListNode a, ListNode b) {
        ListNode pre, cur, nxt;
        pre = null;
        cur = a;
        nxt = a;
        // while 终止的条件改一下就行了
        while (cur != b) {
            nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        // 返回反转后的头结点
        return pre;
    }


    public ListNode reverseList(ListNode a, ListNode b) {
        if (a == b) {
            return a;
        }
        // 反转当作后续遍历
        ListNode last = reverseList(a.next, b);
        ListNode finallyNode = last.next;
        // 交换两个节点之间的箭头（指向）
        a.next.next = a;
        a.next = finallyNode;

        return last;
    }


    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
